A. Technical Field
The present invention relates generally to associative memories, and in particular to content addressable memories. More particularly, the present invention relates to an associative memory having a match resolution circuit for determining a best match from among multiple matches.
B. Background of the Invention
An associative memory, such as a content addressable memory (CAM), is a device that permits the contents of the memory to be searched and matched instead of having to specify a memory location address in order to retrieve data from the memory. A CAM may be used to accelerate any application requiring fast searching of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. A CAM provides a performance advantage over conventional memory devices with conventional memory search algorithms, such as binary or tree-based searches, by comparing the desired information against the entire list of entries simultaneously, giving an order-of-magnitude reduction in search time. For example, a binary search through a database of 1000 entries may take ten separate search steps whereas a CAM device with 1000 entries may be searched in a single operation resulting in a search which takes ten times less time. One example of an application in which CAM devices are often used is to store a routing table for high speed switching systems which need to rapidly search the routing table to look for a matching destination address so that a data packet may be routed to the appropriate destination address.
A CAM device is organized somewhat differently from typical SRAM or DRAM devices. Information stored in a CAM may be accessed by comparing the data stored in the memory with data placed in a special register known as a search input or compare register as opposed to RAM devices in which information is accessed by specifying a particular memory address. If there is a match in particular memory locations with every corresponding bit in the register, a Match Flag is asserted to let the user know that the data in the register was found in the CAM device. Thus, with a CAM device, the user supplies a piece of data she would like to match to the CAM and gets back the address of any matching pieces of data in the CAM. There are two common types of CAM memory, binary CAM and ternary CAM. Binary cam requires an exact match of all bits in the search input and comparand for a match. Ternary CAM uses a mask to allow some bits to be treated as xe2x80x9cdon""t carexe2x80x9d bits and ignored in the determination of a match.
Data in a Binary CAM location typically comprises 2 fields: a comparand and an associated data field. Unlike a random access memory (xe2x80x9cRAMxe2x80x9d), when a search is performed on a CAM, all comparands in a CAM are compared simultaneously with a search input stored in a register. As each comparand is compared with the search input, a match line for that comparand is activated if the comparand matches the search word. Prior art ternary CAM devices may also contain an additional field known as a mask. The mask may be used to filter off portions of the comparand during the search procedure. In other words, the mask allows a comparison between the search input and only certain portions of the comparand as determined by the mask.
A search on a CAM may result in several matches in response to the search input, however, only one result should be returned. Therefore, one problem in the prior art is determining which match from a plurality of matches should be returned as the best match for a particular search input. One solution in the prior art is to implement a priority resolution circuit that uses the position of the data item in the CAM array to determine which match to output. One disadvantage in using a priority resolution circuit based on the position of the data item in the CAM array is that it only offers one criteria, (i.e. position) for determining a best match. Additionally, in order to change the priority of a particular CAM data item, it is necessary to move the data items to different positions in the CAM array. This process is cumbersome and slows down the operation of the CAM. Accordingly it is desirable to provide a priority resolution system that is capable of determining a best match among a plurality of CAM matches. More specifically, it is advantageous to provide a priority resolution system that can be dynamically updated and can use criteria other than position to determine a best match among a plurality of matches.
The present invention overcomes the deficiencies and limitations of the prior art with a unique system and method for determining a best match from a plurality of matches resulting in response to a search input performed on an associative memory. The system and method for determining a best match from a plurality of matches comprises a priority field associated with each data item stored in the associative memory. The priority field corresponds to criteria that is used to order the priority of the data items. A match resolution module is coupled to receive match signals from an associative memory and the priority fields associated with the matching data entries. The match resolution structure compares the priority fields of the plurality of matching data items to determine which data item has the highest priority. The match resolution structure then indicates the data item having the highest priority as the best match of the associative memory for the particular search input.